package Datastruct.Algorithm.recursion;


/**
 * 递归实现迷宫问题
 */
public class MazeApp {

    public static void main(String[] args) {

        /**
         * 八行七列
         * 墙设置为1
         */
        int [][] map=new int[8][7];
        for(int i=0;i<7;i++){
            map[0][i]=1;
            map[7][i]=1;
        }
        for(int i=0;i<8;i++){
            map[i][0]=1;
            map[i][6]=1;
        }
        map[3][1]=1;
        map[3][2]=1;
        map[5][3]=3;

        for (int i=0;i<8;i++){
            for (int j=0;j<7;j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println(System.currentTimeMillis());
        isRun(map,1,1);
        System.out.println("小球走过的路径是：");
        for(int i=0;i<8;i++){
            for(int j=0;j<7;j++){
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println(System.currentTimeMillis());

    }

    /**
     *     1.小球从 那个位置开始触发 起始位置 1,1
     *     2.  map是地图对象
     *     3、 最终小球到达了 6,5
     *     4.元素为0表示没有走过 元素为1表示是墙，元素为2表示通过可以走，3表示不可以
     * @param map
     * @param i
     * @param j
     * @return
     */
    public static   boolean  isRun(int [][]map ,int i,int j){
            if(map[6][5]==2){
                return true;
            }else{
                if(map[i][j]==0){
                    map[i][j]=2;

                    //  下 右 上 左
                    if(isRun(map,i+1,j)){
                        return  true;
                    }else  if(isRun(map,i,j+1)){
                        return  true;
                    }else  if(isRun(map,i-1,j)){
                        return  true;
                    }else  if(isRun(map,i,j-1)){
                        return  true;
                    }else {
                        if(map[i][j]==3){
                            return  false;
                        }
                    }
                }else {
                    return  false;
                }
            }
            return  false;
    }
}
